package architect.datastructure;

/**
 * 双向链表
 *
 * @author guanxin
 * @date 2018/5/7 11:30
 */

public class DoubleLinkedList {
    // 链表节点
    private class Node {
        Object item; // 节点元素
        Node prev;   // 上一节点
        Node next;   // 下一节点

        public Node() { }

        public Node(Object item, Node prev, Node next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }

    Node first;  // 链表头节点
    Node last;   // 链表尾节点
    int size;    // 链表的长度

    public DoubleLinkedList() {
        this.first = null;
        this.last = null;
        this.size = 0;
    }

    public DoubleLinkedList(Node first, Node last, int size) {
        super();
        this.first = first;
        this.last = last;
        this.size = size;
    }

    public void checkIndex(int index) {
        if (index < 0 || index >= size) {
            try {
                throw new Exception("索引超界");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

    public Node getNode(int index) {
        Node node = this.first;
        if (first != null) {
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        }
        return node;
    }

    public void add(Object o) {
        Node node = new Node();
        if (first == null) {
            node.item = o;
            node.prev = null;
            node.next = null;
            first = node;
            last = node;
        } else {
            node.item = o;
            node.prev = last;
            node.next = null;
            last.next = node;
            last = node;
        }
        size++;
    }

    public void add(int index, Object o) {
        Node originalNode = getNode(index);
        Node node = new Node();
        if (originalNode != null) {
            node.item = o;
            node.prev = originalNode.prev;
            node.next = originalNode;
            originalNode.prev = node;
            //originalNode.prev.next = node;
        }
        size++;
    }

    public Object get(int index) {
        checkIndex(index);
        return getNode(index).item;
    }

    public void remove(int index) {
        checkIndex(index);
        Node node = getNode(index);
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
    }

    public void set(int index, Object o) {
        checkIndex(index);
        Node node = getNode(index);
        if (node != null)
            node.item = o;
    }
}
